package leetcode.每日一题;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/10/11 22:25
 * @description：
 */
public class 另一棵树的子树 {
    @Test
    public void test() {
        Solution solution = new Solution();

    }

    /*class Solution {
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            return dfs(root, subRoot);
        }

        private boolean dfs(TreeNode s, TreeNode t) {
            if (s == null) return false;
            return check(s, t) || dfs(s.left, t) || dfs(s.right, t);
        }

        private boolean check(TreeNode s, TreeNode t) {
            if (s == null && t == null) return true;
            if (s == null || t == null || s.val != t.val) return false;
            return check(s.left, t.left) && check(s.right, t.right);
        }
    }*/

    class Solution {
        private StringBuilder sBuilder = new StringBuilder();
        private StringBuilder tBuilder = new StringBuilder();
        public boolean isSubtree(TreeNode s, TreeNode t) {
            getPreFix(s, sBuilder);
            getPreFix(t, tBuilder);
            System.out.println(sBuilder);
            System.out.println(tBuilder);
            return sBuilder.toString().contains(tBuilder);
        }

        private void getPreFix(TreeNode node, StringBuilder builder) {
            if (node == null) return;
            builder.append(node.val);
            if (node.left != null) {
                getPreFix(node.left, builder);
            } else {
                builder.append("lNull");
            }
            if (node.right != null) {
                getPreFix(node.right, builder);
            } else {
                builder.append("rNull");
            }
        }
    }
}
